题面

题目描述

幻想历$8012$年$5$月$12$日深夜，斯普林·布拉泽降下神谕：$“Trust\ me, earn\ eternal\ life.”$ 克里斯军团士气大增。作为克里斯军团的主帅，你决定利用这一机会发动奇袭，一举击败杰森国。具体地说，杰森国有 $N$ 个城市，由 $M$ 条单向道路连接。神谕镇是城市 $1$ 而杰森国的首都是城市 $N$。你只需摧毁位于杰森国首都的曾·布拉泽大神殿，杰森国的信仰，军队还有一切就都会土崩瓦解，灰飞烟灭。

为了尽量减小己方的消耗，你决定使用自爆机器人完成这一任务。唯一的困难是，杰森国的一部分城市有结界保护，不破坏掉结界就无法进入城市。而每个城市的结界都是由分布在其他城市中的一些结界发生器维持的，如果想进入某个城市，你就必须破坏掉维持这个城市结界的所有结界发生器。

现在你有无限多的自爆机器人，一旦进入了某个城市，自爆机器人可以瞬间引爆，破坏一个目标（结界发生器，或是杰森国大神殿），当然机器人本身也会一起被破坏。你需要知道：摧毁杰森国所需的最短时间。

输入输出格式

输入格式：

输入文件的 $landcraft.in$ 的第一行两个正整数 $N, M$。

接下来 $M$ 行，每行三个正整数 $ui, vi, wi$，表示有一条从城市 $ui$ 到城市 $vi$ 的单向道路，自爆机器人通过这条道路需要 $wi$ 的时间。

之后 $N$ 行，每行描述一个城市。首先是一个正整数 $li$，维持这个城市结界所使用的结界发生器数目。之后 $li$ 个 $1~N$ 之间的城市编号，表示每个结界发生器的位置。如果 $li = 0$，则说明该城市没有结界保护，保证 $l1 = 0$。

输出格式：

输出文件 $landcraft.out$ 仅包含一个正整数 ，击败杰森国所需的最短时间。

输入输出样例

输入样例#1：

6 6
1 2 1
1 4 3
2 3 1
2 5 2
4 6 2
5 3 2
0
0
0
1 3
0
2 3 5

输出样例#1：

5

说明

img

img

对于 $20\%$的数据，满足 $N\le15$，$M\le50$；

对于 $50\%$ 的数据，满足 $N\le500$，$M\le6,000$；

对于 $100\% $的数据，满足 $N\le3,000$，$M\le70,000$，$1\le wi\le10^8$。

输入数据保证一定有解，且不会存在维持某个城市结界的结界发生器在这个城市内部。

连接两个城市的道路可能不止一条，也可能存在一个城市自己到自己的道路。

解题思路

$Dijksra$，可以说是一道比较好的最短路吧

对于控制其他城市结界这种情况，果断连边，当然啦，这些边是不跑图的

然后怎么处理只有结界破坏后才能跑图呢？

这就想到了 $Dijskstra$的性质，对于每个点，只拿它更新了一次，并且，我们一同更新结界的情况，这样就可以保证，每次更新结界的时间，肯定是最短的，那么所有结界全部被破坏的情况就可以用一个数组记录了，$lim[i]$ 表示 $i$ 这个点所有结界都被破坏的最短时间，而它又是每个结界被破坏的最短时间的最大值（有点绕，仔细理解一下），那么就取 $max$ 即可

跑图的时候注意：对于结界还没全部被破坏的城市不能跑（但是能更新 $d[i]$，也就是先得出最短路答案，最后再判断这个最短距离所用的时间是否大于结界全部被破坏的时间

总体来说还是比较简单的，但是关于 $long\ long$类型赋极大值问题这里还是要$\%$一波 $Judge$ 巨佬

Code

#include<bits/stdc++.h>
#define INF 1000000000000000000
#define rgt register
#define ll long long
#define M 70003
#define N 3003
using namespace std;
struct Edge{
    int to,nxt,cost;
    Edge(int a,int b):to(a),cost(b){}
    Edge(){}
}b[M<<1];
struct Extent{
    int to,nxt;
}Ev[M<<1];
struct node{
    int to,cost;
    node(int a,int b):to(a),cost(b){}
    node(){}
    inline bool operator< (const node x) const{
        return cost>x.cost;
    }
};
int head[N],hv[N],a[N][N];
int n,m,t,tv,In[N];
ll d[N],lim[N],y;
bool vis[N];
inline int read() {
    rgt int s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline void add(int x,int y,int cost) {
    b[++t]=Edge(y,cost),b[t].nxt=head[x],head[x]=t;
}
inline void Add(int x,int y) {
    Ev[++tv].to=y,Ev[tv].nxt=hv[x],hv[x]=tv;
}
inline void Dijkstra() {
    int i,cur,to;ll cost;
    priority_queue<node>p;p.push(node(1,0));
    memset(d,0x7f,sizeof(d)),d[1]=0;
    while(!p.empty()) {
        cur=p.top().to,p.pop();
        if(vis[cur]) continue;vis[cur]=1;
        for(i=hv[cur];i;i=Ev[i].nxt) {//处理结界
            to=Ev[i].to,lim[to]=max(lim[to],d[cur]),--In[to];
            if(!In[to]) {
                if(d[to]<INF) {//结界已经炸完了，而且d[to]被跑到过了
                    d[to]=max(d[to],lim[to]);
                    p.push(node(to,d[to]));
                }
            }
        }
        for(i=head[cur];i;i=b[i].nxt) {//跑图
            to=b[i].to,cost=d[cur]+b[i].cost;
            if(!In[to]&&lim[to]>cost) cost=lim[to];
            if(d[to]>cost) {
                d[to]=cost;
                if(!In[to]) p.push(node(to,cost));//结界没炸完的就算了吧
            }
        }
    }
}
int main()
{
    int i,j,x,y;
    n=read(),m=read();
    memset(a,0x7f7f7f7f,sizeof(a));
    for(i=1;i<=m;i++)
        x=read(),y=read(),a[x][y]=min(a[x][y],read());
    for(i=1;i<=n;i++) {//什么重边，自环都搞定
        for(j=1;j<=n;j++) {
            if(a[i][j]==0x7f7f7f7f||i==j)
                continue;
            add(i,j,a[i][j]);
        }
    }
    for(i=1;i<=n;i++) {
        In[i]=read();//类似用于拓扑排序一样
        for(j=1;j<=In[i];j++)
            x=read(),Add(x,i);
    }
    Dijkstra();
    printf("%lld",d[n]);
    return 0;
}

devil.